#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    # 找到第一个1, 然后使用快排的split(如果没有1, 找到第一个0)
    def sortColors(self, nums):
        l = len(nums)
        if l <= 1:
            return

        last_0 = 0                  # last_1 索引之前都是1, 但last_0指向的不是0(下一个可以放入0的位置)
        first_2 = l - 1       # first_2之后的都是2, 但first_2指向的不是2(下一个可以放入2的位置)

        last_1 = 0                  # 最有一个1的位置

        while last_1 <= first_2:
            n = nums[last_1]
            if n == 0:
                nums[last_0], nums[last_1] = nums[last_1], nums[last_0]
                last_0 += 1
                last_1 += 1
            elif n == 1:
                last_1 += 1
            else:
                # assert n == 2
                nums[last_1], nums[first_2] = nums[first_2], nums[last_1]
                first_2 -= 1


def main():
    print("start main")
    s = Solution()
    l = [0, 2, 1, 1, 2]
    s.sortColors(l)
    print(l)


if __name__ == "__main__":
    main()
